package medium完全平方数;

import org.testng.annotations.Test;

public class Solution {
    int count = Integer.MAX_VALUE;
    public int numSquares(int n) {
        int max = (int)Math.sqrt(n);
        if ((int)Math.pow(max,2) == n){
            return 1;
        }
        test(n,0);
        return count;
    }
    public void test(int n, int num){
        int max = (int)Math.sqrt(n);
        for (int i = max; i >= 1; i--) {
            if (n-(int)Math.pow(i,2) == 0){
                num++;
                count = Math.min(num,count);
                return;
            }
            test(n-(int)Math.pow(i,2), num+1);
        }
    }

    public int numSquares1(int n) {
        int[] f = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int minn = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                minn = Math.min(minn, f[i - j * j]);
            }
            f[i] = minn + 1;
        }
        return f[n];
    }

    public int numSquares2(int n) {
        if (isPerfectSquare(n)) {
            return 1;
        }
        if (checkAnswer4(n)) {
            return 4;
        }
        for (int i = 1; i * i <= n; i++) {
            int j = n - i * i;
            if (isPerfectSquare(j)) {
                return 2;
            }
        }
        return 3;
    }

    // 判断是否为完全平方数
    public boolean isPerfectSquare(int x) {
        int y = (int) Math.sqrt(x);
        return y * y == x;
    }

    // 判断是否能表示为 4^k*(8m+7)
    public boolean checkAnswer4(int x) {
        while (x % 4 == 0) {
            x /= 4;
        }
        return x % 8 == 7;
    }



    @Test
    public void test1(){
        System.out.println(numSquares(12));
    }
}
